#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#include <time.h>

#define max(a,b) (((a)>(b)?(a):(b)))

int MAXVALUE = 0;

void Input(int * array, int size)
{
	int  value = 0, cnt;
	char f_size[4096];
	FILE *src;

	if ( (src = fopen("Merge.inp", "rb")) == NULL )
	{
		printf("Merge.inp open error!\n");
		exit(1);
	}
	value = atoi(fgets(f_size,size,src));

	for ( cnt = 0 ; cnt < size ; cnt++)
	{
		value = atoi(fgets(f_size,size,src));
		array[cnt] = value;
		MAXVALUE = max(value,MAXVALUE); 
	}

	fclose(src);
}

void Output(int * array, int size)
{
	int cnt;
	FILE *src;
	
	if ( (src = fopen("Merge.out", "w+b")) == NULL )
	{
		printf("Merge.out open error!\n");
		exit(1);
	}

	for ( cnt = 0 ; cnt < size ; cnt++ )
	{
		fprintf(src,"%d\n", array[cnt]);
	}

	fclose(src);
}

int Merge(int *f_array, int f_start, int f_mdl, int f_end)
{
	int cnt1 = f_mdl-f_start+1;
	int cnt2 = f_end-f_mdl;
	int cnt_in, m_tmp;

	int cnt_m1, cnt_m2, L[cnt1+1], R[cnt2+1];
	for ( cnt_m1 = 0 ; cnt_m1 < cnt1 ; cnt_m1++ )
	{
		L[cnt_m1] = f_array[f_start+cnt_m1];
	}
	for ( cnt_m2 = 0 ; cnt_m2 < cnt2 ; cnt_m2++ )
	{
		R[cnt_m2] = f_array[f_mdl+cnt_m2+1];
	}
	
	L[cnt1] = MAXVALUE+1; 
	R[cnt2] = MAXVALUE+1;
	
	cnt_m1 = cnt_m2 = 0;
	

	for ( cnt_in = f_start ; cnt_in <= f_end ; cnt_in++ )
	{
		if ( L[cnt_m1] == L[cnt1] )
		{
			f_array[cnt_in] = R[cnt_m2++];
			continue;
		} else if ( R[cnt_m2] == R[cnt2] )
		{
			f_array[cnt_in] = L[cnt_m1++];
			continue;
		}
		
		
		if ( L[cnt_m1] > R[cnt_m2] )
		{
			f_array[cnt_in] = R[cnt_m2++];
		} else
		{            
			f_array[cnt_in] = L[cnt_m1++];
		}
	}
	//printf("Merge End\n");
}

int MergeSort(int *f_array, int f_start, int f_end)
{
	int f_mdl=0, f_tmp=0;
	if   ( ( f_end - f_start ) >= 1 )
	{
    		if ( ((float)(f_end + f_start)/2) == (f_end + f_start)/2 )
    		{
    			f_mdl = (f_end + f_start) / 2 ; 
    		} else if ( (f_end - f_start) == 1 )
        	{
        		f_mdl = f_start;
        	} else if ( ((float)(f_end + f_start)/2) > (f_end + f_start)/2 )
    		{        
    			f_mdl = (f_end + f_start-1) / 2 ;
    		}
    	
        	if ( f_end >= f_start )
    		{
    			MergeSort(f_array, f_start, f_mdl);
        		MergeSort(f_array, f_mdl+1, f_end);
       			Merge(f_array, f_start, f_mdl, f_end);            
    		}
	}
}

	
int main()
{
	time_t Tstart, Tend;
	Tstart = clock();

	int cnt, cnt_inp = 0;
	int i_size;
	char size[4096];
	FILE *inp;
   
	inp = fopen("Merge.inp", "rb");
	i_size = atoi(fgets(size,4096,inp)); 
	i_size = atoi(size);

	printf("i_size = %d\n", i_size);

	int * array = (int *)malloc(i_size*sizeof(int));

	fclose(inp);

	Input(array, i_size);
	int start = 0, end = i_size-1;
    /*
	printf("Merge Sort\n\n");
	printf("before : \n%02d", array[(cnt=0)]);
	while ( cnt < MAXARRAY-1 ) printf(", %02d", array[++cnt]);
	puts("");*/
	    
	MergeSort(array, start, end); 	
    /*
   	puts("");    	
	printf("after : \n%02d", array[(cnt=0)]);
	while ( cnt < MAXARRAY-1 ) printf(", %02d", array[++cnt]);
	puts("\n");
	*/

	Output(array, i_size);

	Tend = clock();
	printf("Time elapsed : %lf (seconds)\n", (double)(Tend-Tstart)/CLOCKS_PER_SEC);
	return 0;
}
